Meta-Tunning 3

감소 연산 튜닝
- 단일 변수 줄이기
- 배열 줄이기
- 중첩된 클래스 개체 줄이기
- 추상화 패널티
단일 변수 줄이기
임시 변수는 심각한 병목 현상의 원인이 될 수 있다.

반복 블록의 펑터 관점에서 one_norm 함수
template <unsigned BSize, typename Vector>
typename Vector::value_type inline one_norm(const Vector& v){
using std::abs;
typename Vector::value_type sum(0);
unsigned s=size(v); sb=s/BSize*BSize;
for(unsigned i=0; i<sb; i+=BSize) one_norm_ftor<0, BSize>()(sum ,v ,i);
for(unsigned i=sb; i<s; ++i) sum+=abs(v[i]);
return sum;
}
template <unsigned Offset, unsigned Max>
struct one_norm_ftor{
template <typename S, tpyename V>
void operator()(S& sum, const V& v, unsigned i){
using std::abs;
sum+=abs(v[i+Offset]);
one_norm_ftor<Offset+1, Max>()(sum ,v ,i);
}
};
template <unsigned Max>
struct one_norm_ftor<Max, Max>{
template <typename S, typename V>
void operator()(S& sum, const V& v, unsigned i) {}
};
배열 줄이기
위의 코드는 서로 다른 v의 항목을 사용한다.
하지만, 모든 계산이 동시에 임시 변수 sum에 접근하기 때문에 동시성이 제한된다.
더 많은 동시성을 사용하기 위해서 여러 임시 변수를 사용한다.
template <unsigned BSize, typename Vector>
typename Vector::value_type iline one_norm(const Vector& v){
using std::abs;
typename Vector::value_type sum[BSize];
for(unsigned i=0; i<BSize; ++i) sum[i]=0;
unsigned s=size(v), sb=s/BSize*BSize;
for(unsigned i=0; i<sb; i+=BSize) one_norm_ftor<0, BSize>()(sum, v, i);
for(unsigned i=1; i<BSize; ++i) sum[0]+=sum[i];
for(unsigned i=sb; i<s; ++i) sum[0]+=abs(v[i]);
return sum[0];
}
template <unsigned Offset, unsigned Max>
struct one_norm_ftor{
template <typename S, typename V>
void operator()(S* sum, const V& v, unsigned i){
using std::abs;
sum[Offset]+=abs(v[i+Offset]);
one_norm_ftor<Offset+1, Max>()(sum, v, i);
}
};
template <unsigned Max>
struct one_norm_ftor<Max, Max>{
template <typename S, typename V>
void operator()(S* sum, const V& v, unsigned i) {}
};
위처럼 구현하면, 최종적으로 sum 배열의 합을 구하기 위해서 한번 더 loop를 돌아야 하기 때문에 더 느릴 수도 있다.
중첩된 클래스 개체 줄이기
n개의 임시 변수를 갖는 클래스를 정의하면 배열을 사용하지 않을 수 있다.

타입의 개체를 재귀적으로 초기화할 수 있기 때문에, 배열처럼 반복문이 필요하지 않음
template <unsigned BSize, typename Value>
struct multi_tmp{
typedef multi_tmp<BSize-1, Value> sub_type;
multi_tmp(const Value& v): value(v), sub(v) {}
Value value;
sub_type sub;
Value sum() const { return value+sub.sum(); }
};
template <typename Value>
struct multi_tmp<0, Value>{
multi_tmp(const Value& v){}
Value sum() const { return 0; }
};
// norm functor
template <unsigned Offset, unsigned Max>
struct one_norm_ftor{
template <typename S, typename V>
void operator()(S& sum, const V& v, unsigned i){
using std::abs;
sum.value+=abs(v[i+Offset]);
one_norm_ftor<Offset+1, Max>()(sum.sub, v, i);
}
};
template <unsigned Max>
struct one_norm_ftor<Max, Max>{
template <typename S, typename V>
void operator()(S& sum, const V& v, unsigned i){}
};
// one_norm
template <unsigned BSize, typename Vector>
typename Vector::value_type inline one_norm(const Vector& v){
using std::abs;
typedef typename Vector::value_type value_type;
multi_tmp<BSize, value_Type> multi_sum(0);
unsigned s=size(v), sb=s/BSize*BSize;
for(unsigned i=0 i<sb; i+=BSize) one_norm_ftor<0, BSize>()(multi_sum, v, i);
value_type sum=multi_sum.sum();
for(unsigned i=sb; i<s; ++i) sum+=abs(v[i]);
return sum;
}
펑터에서 value 멤버를 조작하고, sub 멤버의 레퍼런스를 후속 펑터에 전달
multi_sum의 부분합을 합하기 위해서 재귀 함수로 구현

일반화된 multi_tmp
template <unsigned BSize, typename Value>
struct multi_tmp{
template <typename Op>
Value reduce(Op op, const Value& init) const {
return op(value, sub.reduce(op, init));
}
};
template <typename Value>
struct multi_tmp<0, Value>{
template <typename Op>
Value reduce(Op, const Value& init) const {
return init;
}
}
추상화 패널티 다루기
위와 같이 임시변수를 사용한 작업은 임시 변수가 레지스터에 할당될 때에만 이점이 있다.
만약 레지스터에 올라가지 않으면, 레지스터-메모리 트래픽이 추가로 발생하고 캐시 무효화 시그널에 의해
전체 실행 속도가 오히려 떨어질 수 있다.

추상화 패널티(Abstration Penalty)는 추상화로 인해 의미론적으로 동일한 프로그램보다 더 느리게 실행되는
개념이다.

(우리는 항상 성능이 가장 중요한 커널이 추상 수준을 낮췄을 때 더 빨라질 수 있는지 확인해야 한다.)
범용성과 고성능을 갖춘 소프트웨어라면, 범용적인 재사용성과 목표로 하는 성능 사이의 균형을 적절하게 맞춰야 함

레지스터를 사용하면, 자료 구조에서 복잡성을 제외하고, 컴파일러 최적화에 도움을 줄 수 있다.
임시 변수가 레지스터에 저장되는 가장 좋은 기회는 임시 변수를 함수 지역 변수로 선언할 때이다.
inline one_norm(const Vector& v){
typename Vector::value_type s0(0), s1(0), s2(0), ...
}
위처럼 함수에서 선언한 지역 변수를 사용하기 위해
레퍼런스를 회전시키기

one_norm_ftor<0, BSize>()(s0, s1, s2, s3, s4, s5, s6, s7, v, i);
one_norm_ftor<1, BSize>()(s1, s2, s3, s4, s5, s6, s7, s0, v, i);
one_nrom_ftor<2, BSize>()(s2, s3, s4, s5, s6, s7, s0, s1, v, i);
...
template <unsigned Offset, unsigned Max>
struct one_norm_ftor{
template <typename S, typename V>
void operator()(S& s0, S& s1, S& s2, S& s3, S& s4, S& s5, S& s6, S& s7, const V& v, unsigned i){
using std::abs;
s0+=abs(v[i+Offset]);
one_norm_ftor<Offset+1, Max>()(s1, s2, s3, s4, s6, s7, s0, v, i);
}
};
template <unsigned Max>
struct one_norm_ftor<Max, Max>{
template <typename S, typename V>
void operator()(S& s0, S& s1, S& s2, S& s3, S& s4, S& s5, S& s6, S& s7, const V& v, unsigned i){}
};
template <unsigned BSize, typename Vector>
typename Vector::value_type inline one_norm(const Vector& v){
unsigned std::abs;
typename Vector::value_type s0(0), s1(0), s2(0), s3(0), s4(0), s5(0), s6(0), s7(0);
unsigned s=size(v), sb=s/BSize*BSize;
for(unsigned i=0; i<sb; i+=BSize){
one_norm_ftor<0, BSize>()(s0, s1, s2, s3, s4, s5, s6, s7, v, i);
}
s0+=s1+s2+s3+s4+s5+s6+s7;
for(unsigned i=sb; i<s; ++i) s0+=abs(v[i]);
return s0;
}